package com.summli.basic.class03;

/**
 * 给定一个数组arr，和一个整数num(数组内部的)。请把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。
 *
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 */
public class Code03_1_PartitionAndQuickSort {
    public static void main(String[] args) {
        int[] arr = {-2,-5,0,3,0,5,3};
        int partition = partition(arr, 0);
        System.out.println(partition);
    }
    public static int partition(int[] arr,int num){
        if(arr == null && arr.length == 0){
            return -1;
        }
        int l = 0;
        int r = arr.length-1;
        int lessThan = -1;
        while(l <= r){
            if(arr[l]<=num){
                swap(arr,l,++lessThan);
            }
            l++;
        }
        return lessThan;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
